def partition(A, p, q): #q超出末端位置
    k = randint(p, q - 1)
    A[p], A[k] = A[k], A[p]
    x = A[p]
    i = p
    for j in range(p + 1, q): #q=p+1时 range空
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[p], A[i] = A[i], A[p]
    return i

def RANDOMIZED_SELECT(A, p, r, i):
    if p + 1 == r: return A[p]
    q = partition(A, p, r)
    k = q - p + 1
    if i == k: return A[q]
    elif i < k:
        return RANDOMIZED_SELECT(A, p, q, i)
    else:
        return RANDOMIZED_SELECT(A, q + 1, r, i - k)

if __name__=='__main__':
    from random import randint
    A = [3,2,9,0,7,5,4,8,6,1,2,2,2,2]
    print 'A: ', A
    for i in xrange(len(A)):
        print RANDOMIZED_SELECT(A, 0, len(A), i+1),

